module Cpo where

import POrd

import Data.Set


class (POrd a) => Cpo a where
    bottom :: a
    lub    :: a -> a -> a

    -- Laws:
    --
    -- bottom `ple` x for all x::a
    --
    -- x `lub` y = z ==> x `ple` z and x `ple` z and
    --   for all z' with x `ple` z' and y `ple` z': z `ple` z'
    --
    -- All ascending chains must have a least upper bound
    -- in a (completeness property).


instance Ord a => Cpo (Set a) where
    bottom = empty
    lub    = union

instance (Cpo a) => Cpo (Maybe a) where
    bottom                  = Nothing
    Nothing `lub` x         = x
    x `lub` Nothing         = x
    (Just x) `lub` (Just y) = Just (x `lub` y)

instance (POrd a) => Cpo [a] where
    bottom = []
    x `lub` y | x `ple` y = y
              | otherwise = x

